This invention relates to data compression and in particular to multidimensional data representations using vector quantisation.
The next generation of satellite-based remote sensing instruments will produce an unprecedented volume of data. Imaging spectrometers, also known as hyper-spectral imaging devices, are prime examples. They collect image data in hundreds of spectral bands simultaneously from the near ultraviolet to the short wave infrared, and are capable of providing direct identification of surface materials.
Hyper-spectral data thus collected are typically in the form of a three-dimensional (3D) data cube. Each data cube has two dimensions in the spatial domain defining a rectangular plane of image pixels, and a third dimension in the spectral domain defining radiance levels of multiple spectral bands per each image pixel. The volume and complexity of hyper-spectral data present a significant challenge to conventional transmission and image analysis methods. The raw data rates for transmitting such data cubes can easily exceed the available downlink capacity or on-board storage capacity of existing satellite systems. Often, therefore, a portion of the data collected on board is discarded before transmission, by reducing the duty cycle, reducing the spatial or spectral resolution, and/or reducing the spatial or spectral range. Obviously, in such cases large amounts of information are lost.
For data processing, a similar problem occurs. In computing, a current trend is toward desktop computers and Internet based communications. Unfortunately, the data cubes require a tremendous amount of storage and, for processing, the storage is preferably random access memory (RAM). Current desktop computers often lack sufficient resources for data processing of data cubes comprising spectral data.
Recent work related to data compression of multi-spectral and hyper-spectral imagery has been reported in the literature, but most of these studies relate to multi-spectral imagery comprised of only a few spectral bands. These prior art systems for multi-spectral imagery yield small compression ratios, usually smaller than 30:1. There are two reasons for this:
1) the prior art systems do not efficiently remove the correlation in the spectral domain, and
2) the redundancy of multi-spectral imagery in the spectral domain is relatively small compared to that of hyper-spectral imagery.
Gen et al. teach two systems for hyper-spectral imagery. The first system uses trellis coded quantisation to encode transform coefficients resulting from the application of an 8xc3x978xc3x978 discrete cosine transform. The second system uses differential pulse code modulation to spectrally decorrelate data, while using a 2D discrete cosine transform for spatial decorrelation. These two systems are known to achieve compression ratios of greater than 70:1 in some instance; however, it is desirable to have higher compression ratios with simpler coding structures than those reported in the literature.
In an article entitled xe2x80x9cLossy Compression of Hyperspectral Data Using Vector Quantizationxe2x80x9d by Michael Ryan and John Arnold in the journal Remote Sens. Environ., Elsevier Science Inc., New York, N.Y., 1997, Vol. 61, pp. 419-436, an overview of general vector quantization techniques as are now known is presented. The article is herein incorporated by reference. In particular, the authors describe issues such as distortion measures and classification issues arising from lossy compression of hyper-spectral data using vector quantization.
Data compression using Vector Quantisation (VQ) has received much attention because of its promise of high compression ratio and relatively simple structure. Unlike scalar quantisation, VQ requires segmentation of the source data into vectors. Commonly, in two-dimensional (2D) image data compression, a block with nxc3x97m (n may be equal to m) pixels is taken as a vector, whose length is equal to nxc3x97m. Vectors constituted in this way have no physical analogue. Because the blocks are segmented according to row and column indices of an image, the vectors obtained in this manner change at random as the pixel patterns change from block to block. The reconstructed image shows an explicit blocking effect for large compression ratios.
There are several conventional approaches to constituting vectors in a 3D data cube of hyper-spectral imagery. The simplest approach is to treat the 3D data cube as a set of 2D monochromatic images, and segment each monochromatic image into vectors independently as in the 2D-image case. This approach, however, suffers from not taking advantage of the high correlation of data in the spectral domain. There is therefore a need for a data compression system that takes advantage of correlation in the spectral domain and the 2D spatial correlation between adjacent image pixels.
The VQ procedure is known to have two main steps: codebook generation and codevector matching. VQ can be viewed as mapping a large set of vectors into a small cluster of indexed codevectors forming a codebook. During encoding, a search through a codebook is performed to find a best codevector to express each input vector. The index or address of the selected codevector in the codebook is stored associated with the input vector or the input vector location. Given two systems having a same codebook, transmission of the index to a decoder over a communication channel from the first system to the second other system allows a decoder within the second other system to retrieve the same codevector from an identical codebook. This is a reconstructed approximation of the corresponding input vector. Compression is thus obtained by transmitting the index of the codevector rather the codevector itself. Many existing algorithms for codebook designs are available, such as the LBG algorithm reported by Linde, Buzo and Gray, the tree-structure codebook algorithm reported by Gray, the self organising feature map reported by Nasrabadi and Feng. Among these, the LBG algorithm is most widely used because of its fidelity. The disadvantages of the LGB algorithm are its complexity and the time burden taken to form the codebook. When the input data is a 3D data cube of hyper-spectral imagery, the processing time can be hundreds of times higher than the normal 2D-image case.
It is, therefore, an object of the invention to provide a substantially faster method of compression with a relatively high fidelity for encoding multidimensional data.
It is further an object of the invention to provide a method of encoding multidimensional data in a plurality of approximation stages.
In accordance with the invention there is provided, a method for encoding image data using vector quantisation, wherein the encoded image data is compressed data, the method comprising the steps of:
a) determining a first codebook having a plurality of codevectors;
b) encoding each image vector of the image data by determining a codevector within the first codebook that approximates the image vector within the image data;
c) creating a first index map by replacing each image vector with an index indicative of the codevector""s location within the first codebook;
d) determining difference data based on the original image data and the encoded image data; and,
e) repeating the steps of:
e2) determining another codebook;
e2) encoding each error vector of the difference data by determining a codevector within the other codebook that approximates the error vector within the difference data;
e3) creating another index map by replacing each error vector with an index indicative of the codevector""s location within the other codebook; and,
e4) determining new difference data based on the difference data and the encoded difference data;
until a control error of the difference data is smaller than a given threshold.
In accordance with another aspect of the invention there is provided, a method for transmitting encoded image data via a communications network, wherein the encoded image data is compressed data, the method comprising the steps of:
a) receiving from a first station connected to the communications network first data indicative of a first codebook and a first index map;
b) transmitting the first data via the communications network from the first station to a second station; and,
c) repeating the steps of:
c1) receiving data indicative of a consecutive codebook and a consecutive index map; and,
c2) transmitting the data via the communications network from the first station to the second station;
until a fidelity of an image reconstructed from the transmitted data at the second station is above a predetermined threshold or until all codebooks and all index maps of the encoded image data have been transmitted.
In accordance with yet another aspect of the invention there is provided, a method for decoding encoded image data, wherein the encoded image data is compressed data, the method comprising the steps of:
a) decoding each encoded image vector of the image data using a first codebook and a first index map;
b) reconstructing first image data based on the decoded image vectors; and,
c) repeating the steps of:
c1) decoding each encoded error vector of consecutive difference data using a consecutive codebook and a consecutive index map; and,
c2) reconstructing image data based on the first image data and the decoded error vectors of consecutive difference data;
until a fidelity of the reconstructed image data is above a predetermined threshold or until all codebooks and all index maps of the encoded image data have been decoded.
In accordance with the invention there is further provided, a system for encoding image data using vector quantisation, wherein the encoded image data is compressed data, the system comprising:
a first port for receiving the image data;
a processor for:
a) determining a first codebook having a plurality of codevectors;
b) encoding each image vector of the image data by determining a codevector within the first codebook that approximates the image vector within the image data;
c) creating a first index map by replacing each image vector with an index indicative of the codevector""s location within the first codebook;
d) determining difference data based on the original image data and the encoded image data; and,
e) repeating the steps of:
e1) determining another codebook;
e2) encoding each error vector of the difference data by determining a codevector within the other codebook that approximates the error vector within the difference data;
e3) creating another index map by replacing each error vector with an index indicative of the codevector""s location within the other codebook; and,
e4) determining new difference data based on the difference data and the encoded difference data;
until a control error of the difference data is smaller than a given threshold; memory for storing data during execution of steps a) to e4); and, a second port for providing the encoded image data.
In accordance with the invention there is yet further provided, a system for decoding encoded image data, wherein the encoded image data is compressed data, the system comprising:
a first port for receiving the encoded image data;
a processor for:
a) decoding each encoded image vector of the image data using a first codebook and a first index map;
b) reconstructing first image data based on the decoded image vectors; and,
c) repeating the steps of:
c1) decoding each encoded error vector of consecutive difference data using a consecutive codebook and a consecutive index map; and,
c2) reconstructing image data based on the first image data and the decoded error vectors of consecutive difference data;
until a fidelity of the reconstructed image data is above a predetermined threshold or until all codebooks and all index maps of the encoded image data have been decoded;
memory for storing data during execution of steps a) to c2); and, a second port for providing the decoded image data.